/*
数据结构实验二 求解高精度Π
 采用的ADT是双向链表
 CMake如下：

cmake_minimum_required(VERSION 3.27)
project(caculate_PI)
set(CMAKE_CXX_STANDARD 17)
add_executable(caculate_PI main.cpp)

 输入1-500整数
 输出相应位数的圆周率

 Author 孙镇宇
 Time 2024.3.29
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//定义双向链表
typedef int elemtype;
typedef struct DNode{
	struct DNode* prev; //前驱指针
	elemtype data; //数据域
	struct DNode* next;//后驱指针
}DNode ,*PDNode;
//函数声明
PDNode get_tail (PDNode *p);//取得链表的尾部节点地址
void init (PDNode *p , int cnt);//初始化双向链表
void Insert_tail (PDNode *p , int x);//向链表中插入数据（尾插）
void multiply (PDNode *R , int n);//实现高精度乘法
int cnt (int n);//获取迭代次数
void division (PDNode *R , int Divisor);//实现高精度除法
void add (PDNode *R , PDNode *sum);//实现高精度加法
void PRINT (PDNode *p , int n);//经行格式化输出
//程序入口
int main ()
{
	int n;
	scanf ("%d" , &n);
	int k = cnt(n);//取得迭代次数
	PDNode sum = NULL, R = NULL;//定义两个双向链表，sum用于之间得出PI值 ， R为迭代中间变量
	//初始化双向链表
	init(&sum , k + 3);
	init(&R, k + 3);
	PDNode R_tail;
	//输入初始化数据
	R->data = 2;
	sum->data = 2;
	division(&R , 3);
	add(&R , &sum);
	//经行迭代，计算PI值
	for (int i = 2 ; i <= k ; i++)
	{
		R_tail = get_tail(&R);//取得链表尾部，用于乘法
		multiply(&R_tail , i);//高精度乘法
		division(&R , (2*i+1));//高精度除法
		add (&R , &sum);//高精度加法
	}

	PRINT(&sum , n);//格式化输出
	return 0;
}
//实现高精度加法
//R迭代中间变量
//sum存储PI的值v
void add (PDNode *R , PDNode *sum)
{
	//取得两个链表尾部，用于加法
	PDNode R_tem = get_tail(R);
	PDNode sum_tem = get_tail(sum);
	int add;//存储两位加法之后的中间变量
	int carry = 0;//进位记录
	while (R_tem != NULL && sum_tem != NULL)
	{
		add = R_tem->data + sum_tem->data + carry;//两位的加法值计算
		sum_tem->data = add % 10;//更新这一位的数字
		carry = add / 10;//更新进位
		//向下迭代
		R_tem = R_tem->prev;
		sum_tem = sum_tem->prev;
	}
}
//初始化链表，开辟需要迭代的空间
void init (PDNode *p , int cnt)
{
	for (int i = 0 ; i < cnt ; i++)
	{
		Insert_tail(p , 0);
	}
}
//双向链表的尾插法，将数据插入链表尾部
void Insert_tail (PDNode *p , int x)
{
	PDNode head = (*p);
	PDNode temp;//用于临时存储插入节点
	temp = (PDNode)malloc(sizeof(DNode));
	temp->data = x;
	temp->prev = NULL;
	temp->next = NULL;
	if ((*p) == NULL)
	{
		(*p) = temp;
		return;
	}//处理头节点的特殊情况
	while (head->next != NULL)
	{
		head = head->next;
	}//遍历到最后一个节点，进行尾插
	head->next = temp;
	temp->prev = head;
}
//格式化输出，n表示输出位数，p代表指向链表的二级指针
void PRINT (PDNode *p , int n)
{
	//输出整数位和小数点
	PDNode tempnode = (*p);//用于临时存储头节点的地址值
	printf("%d." , tempnode->data);
	tempnode = tempnode->next;
	//对于后续位数的输出
	for(int i = 0 ; i < n ; i++)
	{
		printf ("%d" , tempnode->data);
		tempnode = tempnode->next;
	}
}
//高精度的大数乘法，R是中间迭代的乘法变量，同时也是被乘数，n是乘数
void multiply (PDNode *R , int n)
{
	PDNode tempnode = (*R);//用于临时存储头节点的地址值
	int carry = 0;//进位
	while(tempnode != NULL)
	{
		int tem = tempnode->data * n + carry;//每一位的乘数加上上一次的进位
		carry = tem / 10;//更新进位
		tempnode->data = tem % 10;//更新相应位数的值
		tempnode = tempnode->prev;//向前迭代
	}
}
//高精度除法，R是被除数的ADT，Divisor是除数
void division (PDNode *R , int Divisor)
{
	PDNode temnode = (*R);//用于临时存储头节点的地址值
	int Quotient = 0;//商
	int Remainder = 0;//余数
	while (temnode != NULL)
	{
		Quotient = (temnode->data + 10 * Remainder) / Divisor;//计算商
		Remainder = (temnode->data + (10 * Remainder)) % Divisor;//计算余数
		temnode->data = Quotient;//更新相应位数
		temnode = temnode->next;//向后迭代
	}
}
//用于计算相应迭代次数
int cnt (int n)
{
	int i = 1;
	double  sum = 0;
	int x , y;
	//用于计算余项的精准度
	while (sum < n + 1)
	{
		x = 2 * i + 1;
		y = i;
		sum+=log10(x / y);
		i++;
	}
	return (i + 10);//此处+10是为了有冗余
}
//取得链表尾部，用于实现大数乘法和大数加法。p是操作的链表
PDNode get_tail (PDNode *p)
{
	PDNode temNode = (*p);//用于临时存储头节点的地址值
	//处理空节点的特殊情况
	if (temNode->next == NULL ||temNode ==NULL)
	{
		return (*p);
	}
	//迭代到尾节点
	while (temNode->next != NULL)
	{
		temNode = temNode->next;
	}
	//返回尾节点，即tail
	return temNode;
}
